package vip.zhenzicheng.algorithm.leetcode.binary_search;

/**
 * <a href="https://leetcode.cn/problems/search-in-rotated-sorted-array/">搜索旋转排序数组 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-07-17 13:36
 */
public class SearchInRotatedSortedArray_33 {

  /*二分查找*/
  public int search(int[] nums, int target) {
    int start = 0, end = nums.length - 1;
    while (start <= end) {
      int mid = (start + end) / 2;
      int midVal = nums[mid];

      if (target == midVal) { // 刚好命中
        return mid;
      }

      // 判断是否target和二分中间值都在同一侧，也即都大于或者都小于nums[0]
      boolean isSameSide = (midVal < nums[0] == target < nums[0]);
      // 不在一侧就需要缩区间，正无穷或负无穷
      if (!isSameSide) {
        midVal = (target < nums[0] ? Integer.MIN_VALUE : Integer.MAX_VALUE);
      }
      // 二分
      if (target < midVal) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    }
    return -1; // 没找见
  }

  /*基于数组一半有序，因为无论怎么旋转最少也会有一半数组是有序的*/
  // public int search(int[] nums, int target) {
  //   int start = 0;
  //   int end = nums.length - 1;
  //   while (start <= end) {
  //     int mid = (start + end) / 2;
  //     if (target == nums[mid]) {
  //       return mid;
  //     }
  //
  //     // 左半段有序
  //     if (nums[start] <= nums[mid]) {
  //       if (target >= nums[start] && target < nums[mid]) { // 确定在左区间
  //         end = mid - 1;
  //       } else {
  //         start = mid + 1;
  //       }
  //     }
  //     // 右半段有序
  //     else {
  //       if (target > nums[mid] && target <= nums[end]) { // 确定在右区间
  //         start = mid + 1;
  //       } else {
  //         end = mid - 1;
  //       }
  //     }
  //   }
  //   return -1;
  // }
}
